﻿#include<iostream>
#include<vector>
using namespace std;

//【题目】力扣343.整数拆分
//【难度】中等
//【提交】https://leetcode.cn/problems/integer-break/submissions/672444657/
//【标签】数学；动态规划
class Solution 
{
public:
    int integerBreak(int n) 
    {
        vector<int>dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            for (int j = 1; j < i - 1; j++)
            {
                dp[i] = max({ dp[i],dp[i - j] * j,j * (i - j) });
            }
        }
        return dp[n];
    }
};

/*
学习总结：
通过维护一个 dp 数组，其中 dp[i] 表示将整数 i 拆分为至少两个正整数后所能得到的最大乘积
状态转移的关键在于，对于每个 i，我们枚举其拆分出的第一个数 j，并比较三种情况：
不拆分剩余部分（j * (i - j)）、拆分剩余部分（j * dp[i - j]）以及当前已知的最大值。
这种方法确保了在 O(n²) 的时间复杂度内找到最优解，体现了动态规划“以空间换时间”和利用子问题最优解构建全局最优解的核心思想。
*/